//不使用任何库函数，设计一个跳表。 
//
// 跳表是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想
//与链表相似。 
//
// 例如，一个跳表包含 [30, 40, 50, 60, 70, 90]，然后增加 80、45 到跳表中，以下图的方式操作： 
//
// 
//Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons 
//
// 跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(
//n))，空间复杂度是 O(n)。 
//
// 在本题中，你的设计应该要包含这些函数： 
//
// 
// bool search(int target) : 返回target是否存在于跳表中。 
// void add(int num): 插入一个元素到跳表。 
// bool erase(int num): 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。 
//
// 
//
// 了解更多 : https://en.wikipedia.org/wiki/Skip_list 
//
// 注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。 
//
// 样例: 
//
// Skiplist skiplist = new Skiplist();
//
//skiplist.add(1);
//skiplist.add(2);
//skiplist.add(3);
//skiplist.search(0);   // 返回 false
//skiplist.add(4);
//skiplist.search(1);   // 返回 true
//skiplist.erase(0);    // 返回 false，0 不在跳表中
//skiplist.erase(1);    // 返回 true
//skiplist.search(1);   // 返回 false，1 已被擦除
// 
//
// 约束条件: 
//
// 
// 0 <= num, target <= 20000 
// 最多调用 50000 次 search, add, 以及 erase操作。 
// 
// Related Topics 设计 
// 👍 45 👎 0

package com.leetcode.editor.cn;

import java.util.Random;

//Java：设计跳表
class P1206DesignSkiplist {
    public static void main(String[] args) {
        Skiplist solution = new P1206DesignSkiplist().new Skiplist();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Skiplist {
        //默认初始化头节点
        Node HEAD = new Node(-1);
        //头节点
        Node head;
        //层级
        int levels;

        public Skiplist() {
            head = HEAD;
            levels = 1;
        }

        public boolean search(int target) {
            Node node = head;
            while (node != null) {
                //同一层级查找
                while (node.right != null && node.right.value < target) {
                    node = node.right;
                }
                Node right = node.right;
                if (right != null && right.value == target) {
                    return true;
                }
                node = node.down;
            }
            return false;
        }

        public void add(int num) {
            Node node = head;
            //存储每次向下跳转时的节点
            Node[] nodes = new Node[levels];
            int i = 0;
            while (node != null) {//node为null,表示到达最底层的原链表
                //同一层级查找
                while (node.right != null && node.right.value < num) {
                    node = node.right;
                }
                nodes[i++] = node;
                //继续查找下一层
                node = node.down;
            }
            //插入新节点
            node = nodes[--i];
            Node newNode = new Node(num);
            newNode.right = node.right;
            node.right = newNode;
            //抛硬币决定是否创建索引
            addIndexByCoinFlip(newNode, nodes, i);
        }

        /**
         * 创建索引
         *
         * @param newNode 新插入的节点
         * @param nodes   向下跳转的节点数组
         * @param i       索引层
         */
        private void addIndexByCoinFlip(Node newNode, Node[] nodes, int i) {
            Node downNode = newNode;
            Random random = new Random();
            int coins = random.nextInt(2);
            while (coins == 1 && i > 0) {
                //数组的倒数第二个元素
                Node preNode = nodes[--i];
                Node newIndex = new Node(newNode.value, preNode.right, downNode);
                preNode.right = newIndex;
                downNode = newIndex;
                coins = random.nextInt(2);
            }
            //创建新的索引层级
            if (coins == 1) {
                Node newIndex = new Node(newNode.value, null, downNode);
                Node newHead = new Node(-1, newIndex, head);
                head = newHead;
                levels++;
            }
        }

        public boolean erase(int num) {
            boolean erase = false;
            Node node = head;
            while (node != null) {
                //同一层级查找,获取目标节点的前一个节点
                while (node.right != null && node.right.value < num) {
                    node = node.right;
                }
                //如果找到
                Node right = node.right;
                if (right != null && right.value == num) {
                    //找到num,删除
                    //当前节点右指针指向要删除节点的右节点
                    node.right = right.right;
                    right.right = null;
                    erase = true;
                }
                //继续，删除下一层
                node = node.down;
            }
            return erase;
        }
    }
    class Node {
        int value;
        Node right;
        Node down;

        public Node(int value) {
            this(value, null, null);
        }

        public Node(int value, Node right, Node down) {
            this.value = value;
            this.right = right;
            this.down = down;
        }
    }
    /**
     * Your Skiplist object will be instantiated and called as such:
     * Skiplist obj = new Skiplist();
     * boolean param_1 = obj.search(target);
     * obj.add(num);
     * boolean param_3 = obj.erase(num);
     */
//leetcode submit region end(Prohibit modification and deletion)


}